The present invention relates to network routing and, more specifically, to deadlock-free routing on arbitrary network topologies using edge-disjoint sub-networks.
Ethernet networks are typically employed in local area networks (LANs) that include a plurality of configurable switches. An enhancement to Ethernet, called data center bridging (DCB), converged enhanced Ethernet (CEE) or data center Ethernet (DCE)—but referred to generally herein as DCB, supports the convergence of LANs with storage area networks (SANs). DCB augments standard Ethernet with a per-hop flow control protocol to ensure that packets are never dropped due to switch buffer overflow. DCB's per-hop flow control mechanism is based on “backpressure”—a receiving port issues a pause frame to the sending port if its buffer occupancy exceeds a fixed threshold. After receiving a pause frame, the sending port ceases transmission until the pause expires, typically on the timescale of a few packets worth of transmission time. If the sending switch's buffer reaches the occupancy threshold, it sends pause frames upstream, thus propagating the backpressure. Traditional Ethernet avoids deadlocks by dropping packets when buffer space is not available; however, dropping packets is not an option in lossless networks such as DCB or Infiniband.
When multiple potential paths exist through a group of network nodes (i.e., switches), where each node has a buffer to queue packets, a cycle of buffer dependencies can result in a routing deadlock. For example, in a group of three nodes A, B, C, there can be three paths, A-B-C, B-C-A, and C-A-B. If flows are started on all three paths, buffers at each node can fill and block which results in sending pause packets while waiting for respective buffers to clear at nodes A, B, C. While the routing paths A-B-C, B-C-A, and C-A-B are loop-free, cyclic dependencies can develop when flow A-B-C waits for flow B-C-A, which waits in turn for flow C-A-B. This risk of deadlock may reduce the overall use of lossless Ethernet, particularly for larger network implementations where ensuring deadlock-free routing is more challenging.